Merge Sort - O(NLog(N)) - Divide and Conquer¶
This Divide and Conquer algorithm (comparison-based) splits a List in half,
and keeps splitting the List by 2 until it only has singular elements.
Adjacent elements become sorted pairs, then sorted pairs are merged and
sorted with other pairs as well.
This process continues until we get a sorted list with all the elements
of the unsorted input list.
Explanation:
We recursively split the list in half until we have lists with size one.
We then merge each half that was split, sorting them in the process.
Sorting is done by comparing the smallest elements of each half.
The first element of each list are the first to be compared.
If the first half begins with a smaller value, then we add that to the sorted list.
We then compare the second smallest value of the first half
with the first smallest value of the second half.
Every time we select the smaller value at the beginning of a half,
we move the index of which item needs to be compared by one.
Note that the merge_sort() function returns a New List that is sorted,
rather than sorting the existing list.
Therefore, Merge Sort requires space to create a new list of the same size as the input list.
Time Complexity:
Let’s first look at the merge function. It takes two lists, and iterates N times,
where N is the size of their combined input.
The merge_sort function splits its given array in 2, and recursively sorts the sub-arrays.
As the input being recursed is half of what was given, like binary trees
this makes the time it takes to process grow logarithmically to N.
Therefore the overall time complexity of the Merge Sort algorithm is
O(NLog(N))
def merge(left_list, right_list):
sorted_list = []
left_list_index = right_list_index = 0
# We use the list lengths often, so its handy to make variables
left_list_length, right_list_length = len(left_list), len(right_list)
for _ in range(left_list_length + right_list_length):
if left_list_index < left_list_length and right_list_index < right_list_length:
# We check which value from the start of each list is smaller
# If the item at the beginning of the left list is smaller,
# add it to the sorted list
if left_list[left_list_index] <= right_list[right_list_index]:
sorted_list.append(left_list[left_list_index])
left_list_index += 1
# If the item at the beginning of the right list is smaller,
# add it to the sorted list
else:
sorted_list.append(right_list[right_list_index])
right_list_index += 1
# If we've reached the end of the of the left list,
# add the elements from the right list
elif left_list_index == left_list_length:
sorted_list.append(right_list[right_list_index])
right_list_index += 1
# If we've reached the end of the of the right list,
# add the elements from the left list
elif right_list_index == right_list_length:
sorted_list.append(left_list[left_list_index])
left_list_index += 1
return sorted_list
def merge_sort(LON):
# If the list is a single element, return it
if len(LON) <= 1:
return LON
# Use floor division to get midpoint, indices must be integers
mid = len(LON) // 2
# Sort and merge each half
left_list = merge_sort(LON[:mid])
right_list = merge_sort(LON[mid:])
# Merge the sorted lists into a new one
return merge(left_list, right_list)
Test:
random_LON = [120, 45, 68, 250, 176]
random_LON = merge_sort(random_LON)
print(random_LON)
def mergeSort(NL):
print("Splitting ", NL)
if len(NL) > 1:
mid = len(NL)//2
left_half = NL[:mid]
right_half = NL[mid:]
mergeSort(left_half)
mergeSort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
NL[k] = left_half[i]
i = i + 1
else:
NL[k] = right_half[j]
j = j + 1
k = k + 1
while i < len(left_half):
NL[k] = left_half[i]
i = i + 1
k = k + 1
while j < len(right_half):
NL[k] = right_half[j]
j = j + 1
k = k + 1
print("Merging ",NL)
Test:
NL = [14,46,43,27,57,41,45,21,70]
mergeSort(NL)
print(NL)
Output:
Splitting [14, 46, 43, 27, 57, 41, 45, 21, 70]
Splitting [14, 46, 43, 27]
Splitting [14, 46]
Splitting [14]
Merging [14]
Splitting [46]
-------
Merging [14, 21, 27, 41, 43, 45, 46, 57, 70]
[14, 21, 27, 41, 43, 45, 46, 57, 70]